extends Node2D

@onready var grid_container = $GridContainer
@onready var sum_label = $SumLabel
var grid_size = Vector2(5, 5)  # 5x5网格
var cell_size = 100  # 每个格子的大小
var grid = []
var path = []
var current_path_index = 0
var animation_timer = 0.0
var animation_speed = 0.5  # 动画速度（秒）
var current_sum = 0  # 当前路径和

func _ready():
	generate_grid()
	find_shortest_path()
	current_sum = 0
	update_sum_label()

func update_sum_label():
	sum_label.text = "当前路径和：" + str(current_sum)

func generate_grid():
	# 生成网格和随机数字
	for y in range(grid_size.y):
		var row = []
		for x in range(grid_size.x):
			var cell = ColorRect.new()
			cell.custom_minimum_size = Vector2(cell_size, cell_size)
			# 设置单元格背景为白色，以便数字清晰显示
			cell.color = Color.WHITE
			grid_container.add_child(cell)
			
			# 生成1到9的随机数
			var number = randi() % 9 + 1
			var label = Label.new()
			label.text = str(number)
			
			# 设置字体
			var font = ThemeDB.fallback_font
			var font_size = 48
			label.add_theme_font_override("font", font)
			label.add_theme_font_size_override("font_size", font_size)
			
			# 设置字体颜色为黑色
			label.add_theme_color_override("font_color", Color.BLACK)
			
			# 设置对齐方式和大小
			label.horizontal_alignment = HORIZONTAL_ALIGNMENT_CENTER
			label.vertical_alignment = VERTICAL_ALIGNMENT_CENTER
			label.custom_minimum_size = Vector2(cell_size, cell_size)
			
			cell.add_child(label)
			
			row.append({"node": cell, "value": number})
		grid.append(row)

func find_shortest_path():
	var dp = []
	var prev = []
	
	# 初始化DP数组和前驱数组
	for y in range(grid_size.y):
		dp.append([])
		prev.append([])
		for x in range(grid_size.x):
			dp[y].append(INF)
			prev[y].append(Vector2(-1, -1))
	
	# 设置第一行的初始值
	for x in range(grid_size.x):
		dp[0][x] = grid[0][x]["value"]
	
	# 动态规划计算最短路径
	for y in range(1, grid_size.y):
		for x in range(grid_size.x):
			# 正下方
			if dp[y-1][x] != INF:
				var cost = dp[y-1][x] + grid[y][x]["value"]
				if cost < dp[y][x]:
					dp[y][x] = cost
					prev[y][x] = Vector2(x, y-1)
			
			# 右下方
			if x > 0 and dp[y-1][x-1] != INF:
				var cost = dp[y-1][x-1] + grid[y][x]["value"]
				if cost < dp[y][x]:
					dp[y][x] = cost
					prev[y][x] = Vector2(x-1, y-1)
	
	# 找到最后一行中的最小值
	var min_cost = INF
	var min_x = 0
	for x in range(grid_size.x):
		if dp[grid_size.y - 1][x] < min_cost:
			min_cost = dp[grid_size.y - 1][x]
			min_x = x
	
	# 回溯构建路径
	var current = Vector2(min_x, grid_size.y - 1)
	while current.y >= 0:
		path.append(current)
		if current.y == 0:
			break
		current = prev[current.y][current.x]
	
	path.reverse()

func _process(delta):
	if current_path_index < path.size():
		animation_timer += delta
		if animation_timer >= animation_speed:
			animation_timer = 0.0
			var pos = path[current_path_index]
			grid[pos.y][pos.x]["node"].color = Color.RED
			# 确保路径上的数字保持黑色
			var label = grid[pos.y][pos.x]["node"].get_child(0)
			label.add_theme_color_override("font_color", Color.BLACK)
			
			# 更新路径和
			current_sum += grid[pos.y][pos.x]["value"]
			update_sum_label()
			
			current_path_index += 1
